package offer_test_40;

//实现函数复制一个复杂链表。在复杂链表中，每个结点除了有一个next指针指向下一个结点外，还有一个指向链表中任意结点或null。
public class six_CopyComplexList {
	class ComplexListNode {
		int data;
		ComplexListNode next;
		ComplexListNode other;
	}

	public ComplexListNode clone(ComplexListNode head) {
		cloneNode(head);
		connectSiblingNodes(head);
		return reconnectNodes(head);
	}

	public void cloneNode(ComplexListNode head) {
		ComplexListNode node = head;
		while (node != null) {
			ComplexListNode insertnode = new ComplexListNode();
			insertnode.data = node.data;
			insertnode.next = node.next;
			insertnode.other = null;
			node.next = insertnode;
			node = insertnode.next;
		}
	}

	public void connectSiblingNodes(ComplexListNode head) {
		while(head!=null){
			ComplexListNode node=head.next;
			if(head.other!=null){
				node.other=head.other.next;
			}
			head=node.next;
			
		}
	}

	public ComplexListNode reconnectNodes(ComplexListNode head) {
		ComplexListNode node=head;
		ComplexListNode clonedHead=null;
		ComplexListNode clonedNode=null;
		if(node!=null){
			clonedNode=node.next;
			clonedHead=clonedNode;
			node.next=clonedNode.next;
			node=node.next;
		}
		while(node!=null){
			clonedNode=node.next;
			clonedNode=clonedHead.next;
			node.next=clonedNode.next;
			node=node.next;
		}
		return clonedHead;
	}

	public static void main(String[] args) {
		ComplexListNode root = new six_CopyComplexList().new ComplexListNode();
		ComplexListNode node1 = new six_CopyComplexList().new ComplexListNode();
		ComplexListNode node2 = new six_CopyComplexList().new ComplexListNode();
		ComplexListNode node3 = new six_CopyComplexList().new ComplexListNode();
		ComplexListNode node4 = new six_CopyComplexList().new ComplexListNode();
		root.data = 1;
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		root.data = 1;
		node1.data = 2;
		node2.data = 3;
		node3.data = 4;
		node4.data = 5;
		root.other = node1;
		node1.other = root;
		node3.other = node1;
		six_CopyComplexList test=new six_CopyComplexList();
		ComplexListNode result=test.clone(root);
		System.out.println(result.data);
	}
}
